/*
 * Shellsort
 * Сортировка Шелла
 */

#include <stdio.h>
#include <stdlib.h>

#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))

int shellsort(array, n) /* oh, and by the way.. */
	long long int *array;
	int n;
{
	int gap, i, k;

	for (gap = 1; gap < n; gap = 3 * gap + 1);
	while (gap > 0) {
		gap /= 3;
		for (i = gap; i < n; i++)
			for (k = i - gap; k >= 0 && array[k] > array[k + gap];
					k -= gap)
				SWAP_INT(array[k], array[k + gap]);
	}
	return 0;
}


int
main(argc, argv) /* by the way.. */
	int argc;
	char **argv;
{
	long long *array;
	int size = 1; /* values of *array are 'long long', indexes are 'int' */
	register int i = 0;
	char delimiter = '\n';

	if (argc == 1) {
		fputs("Wtf?\n", stderr);
		return 2;
	}
	size = atol(argv[1]); /* setting amount of elements to sort via cmdline */
	array = malloc(sizeof(long long int) * size);

	for (i = 0; i < size; ++i)
		array[i] = rand() % 1000;

/*	while (i < size)
		scanf("%d", &array[i++] ); */

	shellsort(array, size);

	for (i = 0; i < size; ++i)
		printf("%lld%c", array[i], delimiter);

	free(array); /* cleanup */
	exit(0);
	return 0;
}
